#pragma once
#include <iostream>
#include <string>
#include <algorithm>
#include <assert.h>
using std::cout;
using std::endl;
using std::string;

namespace my_vector
{
    template <class T>
    class vector
    {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;

        void resize(size_t n, T val = T())
        {
            if (n > capacity())
            {
                reserve(n);
                int sz = size();
                for (int i = sz; i < n; i++)
                {
                    _start[i] = val;
                }
                _finish = _start + n;
            }
            else
            {
                _finish = _start + n;
            }
        }
        // reserve是扩容
        void reserve(size_t n)
        {
            if (n < capacity())
            {
                _finish = _start + n;
                return;
            }
            iterator tmp = new T[n];
            int sz = 0;
            if (_start)
            {
                sz = size();
                int i = 0;
                while (_start + i < _finish)
                {
                    tmp[i] = _start[i];
                    i++;
                }
                delete[] _start;
            }

            _start = tmp;
            _finish = _start + sz;
            _end_of_storage = _start + n;
        }

        vector(size_t n)
        {
            reserve(n);
        }

        vector()
        {
            reserve(1);

        }
        vector(size_t n, const T& val)
        {
            resize(n, val);
        }

        void swap(vector& v1)
        {
            std::swap(_start, v1._start);
            std::swap(_finish, v1._finish);
            std::swap(_end_of_storage, v1._end_of_storage);
        }
        vector(const vector& x)
        {
            int sz = x.size();
            reserve(sz);
            for (int i = 0; i < sz; i++)
            {
                _finish[i] = x._start[i];
            }
            _finish += sz;
        }

        template <class InputIterator>
        vector(InputIterator first, InputIterator last)
        {
            InputIterator t = first;
            int n = 0;
            while (t < last)
            {
                n++;
                t++;
            }
            reserve(n);
            for (int i = 0; i < n; i++)
            {
                *(_start + i) = *(first + i);
            }
            _finish = _start + n;
        }

        vector(vector&& x)
        {
            swap(x);
        }

        ~vector()
        {
            delete[] _start;
        }
        iterator begin()
        {
            return _start;
        }

        iterator end()
        {
            return _finish;
        }
        const_iterator begin() const
        {
            return _start;
        }
        const_iterator end() const
        {
            return _finish;
        }

        T& operator[](size_t pos) const
        {
            assert(pos < size());
            return _start[pos];
        }
        vector<T>& operator=(vector<T>& v1) const
        {
            reserve(v1.capacity());
            int sz = v1.size();
            for (int i = 0; i < sz; i++)
            {
                _start[i] = v1[i];
            }
            _finish += sz;
            return *this;

        }
        vector<T>& operator=(vector<T>& v1) 
        {
            reserve(v1.capacity());
            int sz = v1.size();
            for (int i = 0; i < sz; i++)
            {
                _start[i] = v1[i];
            }
            _finish += sz;
            return *this;

        }
        vector<T>& operator=(vector<T>&& v1) const
        {
            swap(v1);
            return *this;
        }
        size_t size() const
        {
            return _finish - _start;
        }
        size_t capacity()
        {
            return _end_of_storage - _start;
        }
        bool empty()
        {
            return _start == _finish;
        }
        void push_back(const T& val)
        {
            if (size() >= capacity())
            {
                int cap = size() == 0 ? 1 : capacity() * 2;
                reserve(cap);
            }
            *_finish = val;
            _finish++;
        }
        void pop_back()
        {
            assert(!empty());
            _finish--;
        }
        template <typename InputIterator>
        iterator insert(iterator position, InputIterator first, InputIterator last)
        {

            assert(position >= _start);
            assert(position <= _finish);
            int n = 0;
            InputIterator tmp = first;
            while (tmp < last)
            {
                n++;
                tmp++;
            }

            // 1 2 3 4
            // 1 2 6 6 6 10 3 4
            T pos = *position;
            if (size() + n >= capacity())
            {
                int cap = capacity();
                while (cap * 2 <= size() + n)
                    cap *= 2;
                reserve(cap);
                position = std::find(begin(), end(), pos);
            }
            int gap = n + size();
            // 扩容之后 position 是一个无效的迭代器
            int sz = gap;
            _finish--;
            while (_finish >= position)
            {
                _start[gap - 1] = *_finish;
                _finish--;
                gap--;
            }
            // 如果传入的是list 迭代器,它内部是没有[]的
            // const int* ++
            iterator t = position;
            for (int i = 0; i < n; i++)
            {
                *t = *first;
                t++;
                first++;
            }
            _finish = _start + sz;
            return position;
        }
        // 1 2 4 4 2 2 3
        // 1 2 2 2 3
        iterator erase(iterator position)
        {
            erase(position, position + 1);
            return position;
        }
        iterator erase(iterator first, iterator last)
        {
            assert(!empty());
            assert(_start <= first);
            assert(_finish >= last);

            iterator cur = last;
            int n = last - first;
            int sz = size() - n;
            while (cur < _finish)
            {
                *first = *cur;
                first++;
                cur++;
            }
            _finish = _start + sz;
            return last;
        }

    private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _end_of_storage = nullptr;
    };

    void fun(const vector<int>& v1)
    {
        vector<int>::const_iterator it = v1.begin();
        while (it != v1.end())
        {
            cout << *it << ' ';
            it++;
        }
        cout << endl;
    }
    void vector_test1()
    {
        vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);

        for (size_t i = 0; i < v.size(); i++)
        {
            cout << v[i] << ' ';
        }
        cout << endl;
        v.pop_back();
        v.pop_back();
        v.push_back(5);
        vector<int>::iterator it = v.begin();
        cout << "-----------------" << endl;
        fun(v);
        v.push_back(6);

        for (auto e : v)
        {
            cout << e << ' ';
        }
        cout << endl;
    }
    // // insert,erase
    void vector_test2()
    {
        vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        for (auto e : v)
        {
            cout << e << ' ';
        }
        cout << endl;
        vector<int>::iterator pos = std::find(v.begin(), v.end(), 3);

        vector<int> v1;
        v1.push_back(6);
        v1.push_back(6);
        v1.push_back(6);
        v1.push_back(10);
        // 1 2 3 4
        // 1 2 6 6 6 10 3 4

        v.insert(pos, v1.begin(), v1.end());
        for (auto e : v)
        {
            cout << e << ' ';
        }
        cout << endl;

        pos = std::find(v.begin(), v.end(), 1);
        v.erase(pos);
        for (auto e : v)
        {
            cout << e << ' ';
        }
        cout << endl;
    }
    // // resize
     void vector_test3()
     {
         vector<int> v;
         v.push_back(1);
         v.push_back(2);
         v.push_back(3);
         v.push_back(4);
         v.resize(10, 5);
         for (auto e : v)
         {
             cout << e << ' ';
         }
         cout << endl;

         for (size_t i = 0; i < v.size(); i++)
         {
             v[i] = 10 + i;
         }

         for (auto e : v)
         {
             cout << e << ' ';
         }
         cout << endl;

         v.resize(1);

         for (auto e : v)
         {
             cout << e << ' ';
         }
         cout << endl;
     }

     class Solution
     {
     public:
         vector<vector<int>> generate(int numRows)
         {
             vector<vector<int>> vv;
             vv.resize(numRows);
             for (size_t i = 0; i < vv.size(); i++)
             {
                 vv[i].resize(i + 1, 0);
                 vv[i][0] = vv[i][vv[i].size() - 1] = 1;
             }
             for (size_t i = 0; i < vv.size(); i++)
             {
                 for (size_t j = 0; j < vv[i].size(); j++)
                 {
                     if (vv[i][j] == 0)
                         vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
                 }
             }
             return vv;
         }
     };

     void vector_test4()
     {
         string s("abc");
         vector<int> v(s.begin(), s.end());
         for (auto e : v)
         {
             cout << e << ' ';
         }
         cout << endl
              << "-----------------------" << endl;

         vector<int> v1(v);
         for (auto e : v1)
         {
             cout << e << ' ';
         }
         cout << endl
              << "-----------------------" << endl;

         vector<int> v2;
         v2 = v1;
         for (auto e : v2)
         {
             cout << e << ' ';
         }
         cout << endl
              << "-----------------------" << endl;

         vector<string> v3(3, "1111");
         for (auto e : v3)
         {
             cout << e << ' ';
         }
         cout << endl
              << "-----------------------" << endl;

         vector<vector<int>> v4 = Solution().generate(5);

         for (size_t i = 0; i < v4.size(); i++)
         {
             for (size_t j = 0; j < v4[i].size(); j++)
             {
                 cout << v4[i][j] << ' ';
             }
             cout << endl;
         }
         cout << endl << "-----------------------" << endl;
     }

} // namespace my_vector
